P3648 [APIO2014]序列分割

发布于 2020-09-23 | 分类于斜率优化 | 3分钟 | 436字数

dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

阅读全文 »

P5504 [JSOI2011]柠檬

发布于 2020-09-23 | 分类于斜率优化 | 4分钟 | 596字数

可以看出，选出区间的端点大小必须相同，不然可以将一端分在其他区间里，答案不会更劣。令

dp_i

表示前

i

个贝壳能得到的最大柠檬数，

pos_i

表示第

i

个贝壳是第几个这种颜色的贝壳。

那么有转移：

阅读全文 »

P4072 [SDOI2016]征途

发布于 2020-09-22 | 分类于斜率优化 | 3分钟 | 449字数

dp[i][j]=min(dp[i-1][k]+(Sum_j-Sum_k)^2) ~~~ (0 \le k < j)

dp[i][j]=min(dp[i-1][k]+Sum_j^2+Sum_k^2-2Sum_iSum_k) ~~~ (0 \le k < j)

阅读全文 »

P2365 & P5785 任务安排

发布于 2020-09-22 | 分类于斜率优化、二分 | 6分钟 | 911字数

两道题的转移式是一样的，只是优化不同。令

dp(i)

为完成前

i

个任务的最小花费。

你会发现每次操作后总时间会增加 $s$ ，这样就不好处理当前时间。

阅读全文 »

第二类斯特林数

发布于 2020-09-18 | 分类于组合数学、斯特林数、多项式 | 6分钟 | 932字数

一.定义

第二类斯特林数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示把 $n$ 个不同的小球放进 $m$ 个相同的盒子里，不能有空盒的方案数。

一些小性质：

阅读全文 »

CF906C Party

发布于 2020-09-17 | 分类于状压dp | 2分钟 | 353字数

首先预处理出一个人能介绍的人的集合 $rel$ 。（包括他本身）

令 $dp(S)$ 表示让集合 $S$ 中的人相互认识最少需要几个人。

那么可以刷表转移：

阅读全文 »

UVA1407 Caves

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 730字数

一道标准的树形dp。

令 $dp[u][i][0/1]$ 表示以 $u$ 为根的子树，探索 $i$ 个洞穴，是否回到 $u$ 。

显然有：

阅读全文 »

CF815C Karen and Supermarket

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 634字数

因为使用优惠劵就必须买这件商品，我们可以将优惠劵的关系看成一棵树。

令 $dp[u][i][0/1]$ 表示以 $u$ 为根的子树，购买 $i$ 件商品， $u$ 是否使用优惠劵的最小花费。

边界条件： $dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]-d[u]$

阅读全文 »

P5176 公约数

发布于 2020-09-12 | 分类于莫比乌斯反演 | 15分钟 | 2336字数

首先有一个结论：

gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}

阅读全文 »

SP1026 FAVDICE - Favorite Dice

发布于 2020-09-12 | 分类于莫比乌斯反演 | 2分钟 | 302字数

令 $dp[i]$ 表示当前已经得到了 $i$ 个面后的期望次数。
有两种情况：

1.掷出已有的面，概率为 $\frac{i}{n}$

阅读全文 »